/**
 * 完全平方数
 *
 * 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
 * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，
 * 其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
 *
 * 示例 1：
 * 输入：n = 12
 * 输出：3
 * 解释：12 = 4 + 4 + 4
 *
 * 示例 2：
 * 输入：n = 13
 * 输出：2
 * 解释：13 = 4 + 9
 *
 * 提示：
 * 1 <= n <= 104
 */

/**
 * 方法 1 :
 * 将 n 看成一个根结点, 然后子节点是小于等于他的每个完全平方数...
 * 这样最后是可以求出来的, 但是这个方法的时间和空间复杂度很大, 即使
 * 我使用了剪枝, 依旧是过不去, 那么我们就要换方法了...
 * 时间复杂度 : O(n * sqrt(n))
 * 空间复杂度 : O(sqrt(n))
 *
 * 方法 2 :
 * 动态规划, 这题也可以看成一个完全背包,
 * dp[i][j] : 表示从前 i 个完全平方数种挑选, 使其总和恰好等于 j, 所有选法中, 平方数的最少数量
 *    不选 i ^ 2 : dp[i][j] = dp[i - 1][j]
 *  选一个 i ^ 2 : dp[i][j] = dp[i - 1][j - i ^ 2] + 1
 *  选两个 i ^ 1 : dp[i][j] = dp[i - 1][j - 2 * j ^ 2] + 2
 *  ....
 *  这里有两种方法可以转化,
 *  第一种就是 dp[i][j] 可以先选一个, 后面继续在 i 个数里面选 => dp[i][j - i ^ 2] + 1
 *  那么 dp[i][j] = min(dp[i - 1][j], dp[i][j - i ^ 2] + 1)
 *  第二种方法就是数学公式的推导了, dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - i ^ 2] + 1, ....)
 *      将 j 换成 j - i ^ 2 => dp[i][j - i ^ 2] = min(dp[i - 1][j - i ^ 2], dp[i - 1][j - 2 * i ^ 2] + 1, ....)
 *      在加上 1 => dp[i][j - i ^ 2] + 1 = .....
 *      可以发现, 下面右边的和上面右右边的相同了, 那么dp[i][j] = min(dp[i - 1][j], dp[i][j - i ^ 2] + 1), 非常巧妙....
 * 时间复杂度 : O(n * sqrt(n))
 * 空间负载的 : O(n * sqrt(n))
 */

public class Main {

    // 方法 2 : 动态规划
    public int numSquares(int n) {

        // 求出最小平方数
        int m = (int) Math.sqrt(n);

        int[][] dp = new int[m + 1][n + 1];

        // 因为后面是要取最小值的, 所以我们要进行初始化
        // 这里初始化为一个用例用不到的最大值
        int INF = 0x3f3f3f3f;
        for (int i = 1; i <= n; i++) {
            dp[0][i] = INF;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= i * i) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - i * i] + 1);
                }
            }
        }

        return dp[m][n];
    }



    // **********************************************************************
    // 方法 1 : DFS + 剪枝
    // 记录最小的平方数的个数
    int minKinds;

    public int numSquares1(int n) {

        // 初始话为 n
        minKinds = n;

        // 深搜
        dfs(n, 0);

        // 返回
        return minKinds;
    }

    public void dfs(int n, int kinds) {

        // 剪枝, 要是不行, 直接结束, 省的后面这么多判断
        if (kinds > minKinds) {
            return;
        }

        // 这里是是函数的出口了, 我们也要在这里更新最终的结果
        if (n == 0) {
            minKinds = Math.min(minKinds, kinds);
        }

        // 这里求出最小的大于等于他的完全平方数
        int k = 1;
        while (k * k < n) {
            k++;
        }

        // 要是大于直接 --, 小于了就不用 --了
        if (k * k > n) {
            k--;
        }

        // 遍历这些平方数, 也就是一个一个遍历吧
        for (int i = k; i >= 1; i--) {
            dfs(n - i * i, kinds + 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(Math.sqrt(10));
    }
}